package personal_exercise;

import model.Node;
import model.TreeNode;

import java.util.*;

public class Demo7 {

    // 501. 二叉搜索树中的众数
//    private TreeNode prev;
    private int count, maxCount;
    private List<Integer> res;
    public int[] findMode(TreeNode root) {
        if (root == null) return new int[0];
        res = new ArrayList<>();
        inorder(root);

        int[] ret = new int[res.size()];
        for (int i = 0, n = res.size(); i < n; i++) {
            ret[i] = res.get(i);
        }
        return ret;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        // 先统计左子树的情况
        inorder(root.left);
        if (prev == null || prev.val != root.val) {
            count = 1;
        } else {
            count++;
        }
        if (count > maxCount) {
            res.clear();
            maxCount = count;
        }
        if (count == maxCount) {
            res.add(root.val);
        }
        prev = root;
        inorder(root.right);
    }


    // 450. 删除二叉搜索树中的节点
    private TreeNode prev;
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        // 寻找值为 key 的结点，并用该结点左子树最右边的结点替换
        if (root.val == key) {
            TreeNode childNode = searchNode(root.left);
            // 左子树为空
            if (childNode == null) return root.right;

            childNode.right = root.right;
            if (childNode != root.left) {
                childNode.left = root.left;
            }
            return childNode;
        }

        TreeNode aimNode = searchAimNode(root, key);
        // 结点不存在
        if (aimNode == null) return root;
        TreeNode childNode = searchNode(aimNode.left);
        // 1) 改变前驱结点的指向
        if (childNode == null) {
            childNode = aimNode.right;
        } else {
            childNode.right = aimNode.right;
            if (childNode != aimNode.left) {
                childNode.left = aimNode.left;
            }
        }
        if (prev.left == aimNode) prev.left = childNode;
        else prev.right = childNode;

        return root;
    }
    private TreeNode searchAimNode(TreeNode root, int key) {
        if (root == null || root.val == key) return root;
        TreeNode left = searchAimNode(root.left, key);
        if (left != null) {
            if (left == root.left) prev = root;
            return left;
        }
        TreeNode right = searchAimNode(root.right, key);
        if (right != null && right == root.right) prev = root;
        return right;
    }
    private TreeNode searchNode(TreeNode root) {
        if (root == null || root.right == null) return root;
        TreeNode prev = root, cur = root.right;
        while (cur.right != null) {
            prev = cur;
            cur = cur.right;
        }
        prev.right = cur.left;
        return cur;
    }



    //  117. 填充每个节点的下一个右侧节点指针 II
    public Node connect(Node root) {
        Node head = root;
        while (head != null) {
            Node newHead = new Node();
            Node tail = newHead;
            while (head != null) {
                if (head.left != null) {
                    tail.next = head.left;
                    tail = tail.next;
                }
                if (head.right != null) {
                    tail.next = head.right;
                    tail = tail.next;
                }
                head = head.next;
            }
            head = newHead.next;
            tail.next = null;
        }
        return root;

    }



    // 129. 求根节点到叶节点数字之和
    private int res1;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return res1;
    }
    private void dfs (TreeNode root, int num) {
        if (root == null) return;
        num = num * 10 + root.val;
        if (root.left == null && root.right == null) {
            res1 += num;
            return;
        }
        dfs(root.left, num);
        dfs(root.right, num);
    }



    // 1026. 节点与其祖先之间的最大差值
    //private int res;
    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return res1;
    }
    private void dfs(TreeNode root, int maxNum, int minNum) {
        if (root == null) return;
        res1 = Math.max(res1, Math.abs(maxNum - root.val));
        res1 = Math.max(res1, Math.abs(minNum - root.val));
        maxNum = Math.max(root.val, maxNum);
        minNum = Math.min(root.val, minNum);
        dfs(root.left, maxNum, minNum);
        dfs(root.right, maxNum, minNum);
    }



    // 1143. 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(), m = text2.length();
        // dp[i][j]: text1中 0 ~ i 区间与text2中 0 ~ j 区间所有子序列中的最长公共子序列的长度
        int[][] dp = new int[n + 1][m + 1];
        char[] arr1 = (" " + text1).toCharArray(), arr2 = (" " + text2).toCharArray();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (arr1[i] == arr2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }



    // 115. 不同的子序列
    public int numDistinct(String s, String t) {
        // dp[i][j]: 在字符串s 0 ~ i 区间的所有子序列中包含字符串t 0 ~ j 的子串的个数
        int n = s.length(), m = t.length();
        char[] arr1 = (" " + s).toCharArray(), arr2 = (" " + t).toCharArray();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (arr1[i] == arr2[j]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m] % (int)(1e9 + 7);
    }
    
    
    
    // 44. 通配符匹配
    public boolean isMatch(String s, String p) {
        //dp[i][j]: 字符串s 0 ~ i 区间和字符串p 0 ~ j 区间的子串能否完全匹配
        int n = s.length(), m = p.length();
        s = " " + s; p = " " + p;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int j = 1; j <= m && p.charAt(j) == '*'; j++) dp[0][j] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j) != '*') {
                    if (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)) dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[n][m];
    }



    // 10. 正则表达式匹配
    public static boolean isMatch2(String ss, String pp) {
        // dp[i][j]: 在字符串p 0 ~ j 区间的子串能否匹配 字符串s的 0 ~ i区间的子串
        int n = ss.length(), m = pp.length();
        ss = " " + ss; pp = " " + pp;
        char[] s = ss.toCharArray(); char[] p = pp.toCharArray();

        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int j = 2; j <= m && p[j] == '*'; j += 2) {
            dp[0][j] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j] == '*') {
                    dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
                } else {
                    if (s[i] == p[j] || p[j] == '.') dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m];
    }




    // 712. 两个字符串的最小ASCII删除和
    public int minimumDeleteSum(String s1, String s2) {
        int sum = 0;
        for (char ch : s1.toCharArray()) sum += ch;
        for (char ch : s2.toCharArray()) sum += ch;
        // dp[i][j]: 字符串s1 0 ~ i 和字符串s2 0 ~ j 区间的所有子序列中最长公共子序列的 ASCII 值和
        int n = s1.length(), m = s2.length();
        s1 = " " + s1; s2 = " " + s2;
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i) == s2.charAt(j)) dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i);
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return sum - 2 * dp[n][m];
    }



    // 918. 环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        int[] f = new int[n + 1], g = new int[n + 1];

        int sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += nums[i - 1];
            f[i] = Math.max(nums[i - 1], f[i - 1] + nums[i - 1]);
            g[i] = Math.min(nums[i - 1], g[i - 1] + nums[i - 1]);
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            max = Math.max(max, f[i]);
            min = Math.min(min, g[i]);
        }
        if(sum == min) return max;
        return Math.max(max, sum - min);
    }



    // 673. 最长递增子序列的个数
    public int findNumberOfLIS(int[] nums) {
        // dp[i]:   以 i 位置为结尾的所有子序列中的最长递增子序列的长度
        // count[i]: 以 i 位置为结尾的所有子序列中的最长递增子序列的个数
        int n = nums.length;
        int[] dp = new int[n], count = new int[n];
        for (int i = 0; i < n; i++) dp[i] = count[i] = 1;

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[i] == dp[j] + 1) count[i] += count[j];
                }
            }
        }

        int maxLen = 0, res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) res += count[i];
            else if (dp[i] > maxLen) {
                res = count[i];
                maxLen = dp[i];
            }
        }
        return res;
    }



    // 646. 最长数对链
    public int findLongestChain(int[][] pairs) {
        // 最长递增子序列
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int n = pairs.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int res = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }



    // LCR 093. 最长的斐波那契子序列的长度
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(arr[0], 0);
        hash.put(arr[1], 1);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = 2;
            }
        }

        int res = 0;
        for (int i = 2; i < n; i++) {
            for (int j = i - 1; j > 0; j--) {
                if (hash.containsKey(arr[i] - arr[j])) {
                    int index = hash.get(arr[i] - arr[j]);
                    dp[j][i] = Math.max(dp[j][i], dp[index][j] + 1);
                    res = Math.max(res, dp[j][i]);
                }
            }
            hash.put(arr[i], i);
        }
        return res == 2 ? 0 : res;

    }



    // 1027. 最长等差数列
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        // dp[i][j]: 以 i 为倒数第二个， j 为倒数第一个数的等差子序列的最大长度
        int[][] dp = new int[n][n];
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) dp[i][j] = 2;
        }
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(nums[0], 0);

        int res = 2;
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int dif = nums[j] - nums[i];
                if (hash.containsKey(nums[i] - dif)) {
                    int k = hash.get(nums[i] - dif);
                    dp[i][j] = dp[k][i] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return res;
    }



    // 446. 等差数列划分 II - 子序列
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        // dp[i][j]: 以 i 为倒数第二个， j 为倒数第一个数的等差子序列的个数
        int[][] dp = new int[n][n];
        // 数字-对应的下标列表
        Map<Integer, List<Integer>> hash = new HashMap<>();
        for (int x : nums) {
            if (!hash.containsKey(x)) hash.put(x, new ArrayList<>());
        }
        hash.get(nums[0]).add(0);

        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                long tmp = 2 * (long)nums[i] - nums[j];
                if (tmp < Integer.MIN_VALUE || tmp > Integer.MAX_VALUE) continue;

                int num = (int)tmp;
                if (hash.containsKey(num)) {
                    for (int index : hash.get(num)) {
                        dp[i][j] += dp[index][i] + 1;
                    }
                    res += dp[i][j];
                }
            }
            hash.get(nums[i]).add(i);
        }
        return res;
    }



    // 1312. 让字符串成为回文串的最少插入次数
    public int minInsertions(String s) {
        // dp[i][j]: 在区间 i ~ j 中，插入若干字符使之成为回文串的最少操作数
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1];
                else dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
            }
        }
        return dp[0][n - 1];
    }



    // 516. 最长回文子序列
    public int longestPalindromeSubseq(String s) {
        // dp[i][j]: 在区间 i ~ j 中，所有回文子序列的最大长度
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }



    // 211. 添加与搜索单词 - 数据结构设计
    class WordDictionary {
        private WordDictionary[] children;
        private boolean isEnd;

        public WordDictionary() {
            children = new WordDictionary[26];
        }

        public void addWord(String word) {
            WordDictionary cur = this;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (cur.children[index] == null) {
                    cur.children[index] = new WordDictionary();
                }
                cur = cur.children[index];
            }
            cur.isEnd = true;
        }

        public boolean search(String word) {
            WordDictionary cur = this;
            return dfs(cur, 0, word);
        }
        private boolean dfs(WordDictionary cur, int pos, String word) {
            if (pos == word.length()) return cur.isEnd;

            for (int i = pos, n = word.length(); i < n; i++) {
                char ch = word.charAt(i);
                if (ch != '.') {
                    int index = ch - 'a';
                    if (cur.children[index] == null) return false;
                    cur = cur.children[index];
                } else {
                    for (int j = 0; j < 26; j++) {
                        if (cur.children[j] != null) {
                            if (dfs(cur.children[j], i + 1, word)) return true;
                        }
                    }
                    return false;
                }
            }
            return cur.isEnd;
        }
    }



    // 437. 路径总和 III
    private int ret;
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        dfs(root, (long)targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return ret;
    }
    private void dfs(TreeNode root, long targetSum) {
        if (root == null) return;
        targetSum -= root.val;
        if (targetSum == 0) ret++;
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
    }


    // JZ61 扑克牌顺子
    public boolean IsContinuous (int[] numbers) {
        boolean[] exists = new boolean[14];
        int min = 14, max = 0;
        int count = 0;
        for (int x : numbers) {
            if (x == 0) count++;
            else {
                if (exists[x]) return false;
                exists[x] = true;
                min = Math.min(min, x);
                max = Math.max(max, x);
            }
        }

        if (max - min - 1 > 3) return false;
        return true;
    }



    // 304. 二维区域和检索 - 矩阵不可变
    class NumMatrix {
        // dp[i + 1][j + 1]: 以(0,0)为左上角，(i,j)为右下角的矩阵的所有元素之和
        private int[][] dp;

        public NumMatrix(int[][] matrix) {
            int n = matrix.length, m = matrix[0].length;
            dp = new int[n + 1][m + 1];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
        }
    }



    // 1314. 矩阵区域和
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n = mat.length, m = mat[0].length;
        // dp[i + 1][j + 1]: 以 (0, 0) 为左上角，(i, j)为右下角的矩形中所有元素之和
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + mat[i][j];
            }
        }

        int[][] res = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int r1 = Math.max(i - k, 0), c1 = Math.max(j - k, 0);
                int r2 = Math.min(i + k, n - 1), c2 = Math.min(j + k, m - 1);
                res[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];
            }
        }
        return res;
    }



    // 2679. 矩阵中的和
    public int matrixSum(int[][] nums) {
        for (int[] arr : nums) Arrays.sort(arr);

        int res = 0;
        int n = nums.length, m = nums[0].length;
        for (int j = 0; j < m; j++) {
            int max = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i][j] > max) max = nums[i][j];
            }
            res += max;
        }
        return res;
    }



    // 132. 分割回文串 II
    public int minCut(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 == j ? true : dp[i + 1][j - 1];
                }
            }
        }
        if (dp[0][n - 1]) return 0;

        // f[i]: 以 i 为结尾的子串分割成回文串的最少次数
        int[] f = new int[n];
        Arrays.fill(f, 0x3f3f3f3f);
        for (int i = 0; i < n; i++) {
            if (dp[0][i]) f[i] = 0;
            else {
                for (int j = i; j > 0; j--) {
                    if (dp[j][i]) f[i] = Math.min(f[i], f[j - 1] + 1);
                }
            }
        }
        return f[n - 1];
    }



    // 1745. 分割回文串 IV
    public boolean checkPartitioning(String s) {
        int n = s.length();
        char[] arr = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) {
                    dp[i][j] = i + 1 == j ? true : dp[i + 1][j - 1];
                }
            }
        }

        for (int i = 0; i < n - 2; i++) {
            if (dp[0][i]) {
                for (int j = i + 1; j < n - 1; j++) {
                    if (dp[i + 1][j] && dp[j + 1][n - 1]) return true;
                }
            }
        }
        return false;
    }



    // LCR 012. 寻找数组的中心下标
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int postSum = 0;
        for (int i = n - 1; i >= 1; i--) {
            postSum += nums[i];
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum == postSum) return i;
            sum += nums[i];
            if (i + 1 < n) postSum -= nums[i + 1];
        }
        return -1;
    }



    // 1207. 独一无二的出现次数
    public boolean uniqueOccurrences(int[] arr) {
        int n = arr.length;
        int[] count = new int[2001];
        for (int x : arr) {
            count[x + 1000]++;
        }

        boolean[] exists = new boolean[1001];
        for (int x : count) {
            if (x != 0 && exists[x]) return false;
            exists[x] = true;
        }
        return true;
    }



    // 941. 有效的山脉数组
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        if (n < 3) return false;
        int i = 0;
        while (i < n - 1 && arr[i] < arr[i + 1]) i++;
        if (i == 0 || i++ == n - 1) return false;
        while (i < n && arr[i] < arr[i - 1]) i++;
        return i < n ? false : true;
    }


    // 1365. 有多少小于当前数字的数字
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n = nums.length;
        Integer[] indexs = new Integer[n];
        for (int i = 0; i < n; i++) indexs[i] = i;
        Arrays.sort(indexs, (a, b) -> nums[a] - nums[b]);

        // 从后向前遍历
        int[] hash = new int[101];
        for (int i = n - 1; i >= 0; i--) {
            hash[nums[indexs[i]]] = i;
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[indexs[i]] = hash[nums[indexs[i]]];
        }
        return res;
    }
}
